package com.example.gdzd_demo.exam;

import com.alibaba.fastjson.JSON;
import lombok.extern.slf4j.Slf4j;
import org.junit.jupiter.api.Test;
import org.springframework.boot.test.context.SpringBootTest;

import java.util.Random;

@SpringBootTest
@Slf4j
public class DrawPrize {

    @Test
    public void testDrawPrize() {
        int[] arr = {20, 34, 160, 2, 50, 100}; // 示例数组
        int winnerId = drawWinner(arr);
        System.out.println();
        log.info("恭喜用户【{}】中奖了！", winnerId);
    }

    public static int drawWinner(int[] arr) {
        if (arr == null || arr.length == 0) {
            throw new IllegalArgumentException("数组为空！");
        }

        // 计算前缀和数组 --前缀和确保每个用户索引的元素唯一
        int[] prefixSum = new int[arr.length];
        prefixSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefixSum[i] = prefixSum[i - 1] + arr[i];
        }
        log.info("前缀数组：{}", JSON.toJSONString(prefixSum));

        // +1确保当等于总积分时，值可以是Max
        Random rand = new Random();
        int randomValue = rand.nextInt(prefixSum[prefixSum.length - 1]) + 1;

        // 查找对应的用户ID --二分查找 时间复杂度O(logn)
        int userId = findUserByScore(randomValue, prefixSum);

        return userId;
    }

    private static int findUserByScore(int score, int[] prefixSum) {
        int left = 0;
        int right = prefixSum.length - 1;

        // 如果当前数组存在随机数，则返回随机数相等的索引；如果不存在，则返回比随机数大且差值最小的索引
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (prefixSum[mid] < score) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

}
